home *** CD-ROM | disk | FTP | other *** search
- /*
- * list management: all entries are kept in lists. A list is a header
- * followed by an array of entries. List sizes are dynamic. Array space
- * is allocated in multiples of CHUNK; if space runs out the list is
- * re-allocated. Copying is done the simple way; let's hope lists don't
- * get too big. There is room for improvement here.
- *
- * Normally, there is one "master list" with everything in the calendar
- * file, from which sublists are created as needed, for example everything
- * on a particular day. Sublists are managed in sublist.c.
- *
- * create_list(list) Start a new list.
- * add_entry(list, entry) Add an entry to a list. This may
- * require realloc'ing the list.
- * delete_entry(list, n) Delete an entry from the list.
- * resort_entry(list, n) Move a particular (newly added or
- * changed) entry to its proper place.
- * rebuild_repeat_chain(list) chain all repeating entries in the
- * list.
- *
- * lookup_entry(lookup, list, time, exact, norep)
- * Find an entry in the list by date.
- * Either finds first, or insert place.
- * lookup_next_entry(lookup) Find the next entry.
- *
- * find_next_trigger(list, time, entryp, wait_time)
- * Find next alarm or warn trigger time.
- * clone_entry(new, old) Copy one entry to another, and all
- * malloced strings in it.
- * destroy_entry(entry) Free all malloced strings of an entry.
- */
-
- #ifndef MIPS
- #include <stdlib.h>
- #endif
- #include <time.h>
- #include <Xm/Xm.h>
- #include "cal.h"
-
- #define CHUNK 100 /* pointer list allocation unit */
-
- extern void fatal();
- extern char *mystrdup();
- extern int recycle();
-
- BOOL lookup_entry(), lookup_next_entry();
-
- time_t cutoff; /* no alarms before this time */
- /* (used by daemon only) */
-
-
- /*----------------------------------- list mgmt -----------------------------*/
- /*
- * create an empty list, with CHUNK blank entries. When the blank entries
- * are all filled, add_entry will allocate more. It's usually enough though.
- */
-
- create_list(list)
- struct list **list; /* pointer to list pointer */
- {
- if (!(*list = (struct list *)malloc(sizeof(struct list) +
- sizeof(struct entry) * CHUNK)))
- fatal("no memory");
- (*list)->modified = FALSE;
- (*list)->locked = FALSE;
- (*list)->nentries = 0;
- (*list)->size = CHUNK;
- (*list)->repeating = -1;
- }
-
-
- /*
- * destroy a list, by freeing all its entries and then the list itself.
- * This is used by the daemon only, which re-reads the database when it
- * gets a HUP signal. Ignore the lint complaint.
- */
-
- destroy_list(list)
- struct list **list; /* pointer to list pointer */
- {
- register int i; /* entry counter */
-
- if (!*list)
- return;
- (*list)->locked++;
- for (i=0; i < (*list)->nentries; i++)
- destroy_entry(&(*list)->entry[i]);
- (*list)->nentries = 0;
- free(*list);
- *list = 0;
- }
-
-
- /*
- * add an entry to a list. The list is kept sorted. Since the list can grow,
- * a pointer to a pointer is passed; the pointed-to pointer changes if the
- * list is re-allocated (or allocated for the first time). To start a new
- * list, pass a pointer to a null pointer; to get rid of a list, free() it.
- * Returns the index to the new entry in the list.
- * Don't forget to call rebuild_repeat_chain(), because this routine is
- * trashing the chain.
- */
-
- add_entry(list, entry)
- struct list **list; /* list to add to */
- struct entry *entry; /* entry to add */
- {
- int num = 0; /* # of entries in old list */
- int size = 0; /* size of allocated old list*/
- struct list *new; /* larger list if required */
- struct lookup lookup; /* result of entry lookup */
- int n; /* index of new entry in list*/
- register struct entry *p, *q; /* entry copy pointers */
- register int i; /* entry copy counter */
-
- if (*list) {
- (*list)->locked++;
- num = (*list)->nentries;
- size = (*list)->size;
- }
- if (num+1 > size) { /* need larger list */
- size += CHUNK;
- if (!(new = (struct list *)malloc(sizeof(struct list) +
- sizeof(struct entry) *size)))
- fatal("no memory");
- if (!*list)
- new->nentries = 0; /* start new list... */
- else {
- new->nentries = num; /* ...or copy old */
- p = (*list)->entry;
- q = new->entry;
- for (i=0; i < num; i++)
- *q++ = *p++;
- }
- new->size = size;
- new->locked = 1;
- if (*list) /* discard old list */
- free(*list);
- *list = new;
- }
- new = *list; /* insert entry */
- n = lookup_entry(&lookup, new, entry->time, FALSE, TRUE)
- ? lookup.index : new->nentries;
- p = &new->entry[n];
- q = &new->entry[new->nentries];
- for (i=new->nentries; i > n; i--, q--)
- q[0] = q[-1];
- clone_entry(p, entry);
- new->nentries++;
- new->repeating = 0;
- new->modified = TRUE;
- new->locked--;
- return(n);
- }
-
-
- /*
- * delete an entry from a list. The list is never re-allocated because lists
- * never shrink, so a simple pointer to a list is expected, and the index to
- * the entry to be deleted.
- * Call rebuild_repeat_chain() afterwards, this routine trashes the chain.
- */
-
- delete_entry(list, n)
- struct list *list; /* list to delete from */
- int n; /* index to entry to delete */
- {
- register struct entry *q; /* entry copy pointer */
- register int i; /* entry copy counter */
-
- list->locked++;
- if (n < 0 || n >= list->nentries) {
- list->locked--;
- return;
- }
- destroy_entry(q = &list->entry[n]);
- for (i=n; i < list->nentries; i++, q++)
- q[0] = q[1];
- list->nentries--;
- list->repeating = 0;
- list->modified = TRUE;
- list->locked--;
- }
-
-
- /*
- * if the time of an entry changed, the list has to be re-sorted. Copy a
- * block if entries to fill the hole, and move the changed entry.
- * Returns the index to the moved entry.
- * Call rebuild_repeat_chain() afterwards, this routine trashes the chain.
- */
-
- resort_entry(list, n)
- struct list *list; /* list to re-sort */
- int n; /* index to changed entry */
- {
- struct lookup lookup; /* result of entry lookup */
- register struct entry *p; /* entry copy pointer */
- register int i; /* entry copy counter */
- struct entry save; /* to save changed entry */
- int d; /* new destination index */
-
- list->locked++;
- if (n < 0 || n >= list->nentries) {
- list->locked--;
- return(0);
- }
- p = &list->entry[n];
- d = lookup_entry(&lookup, list, p->time, FALSE, TRUE)
- ? lookup.index : list->nentries;
- if (d == n) { /* no change? */
- list->locked--;
- return(n);
- }
- save = *p;
- if (d < n) /* move back in time?*/
- for (i=d; i < n; i++, p--)
- p[0] = p[-1];
- else /* move forward? */
- for (i= --d; i > n; i--, p++)
- p[0] = p[1];
- *p = save;
- list->repeating = 0;
- list->modified = TRUE;
- list->locked--;
- return(d);
- }
-
-
- /*
- * rebuild the chain of repeating entries. Repeating entries are chained. The
- * chain is anchored in the entry list struct. Repeating entries should appear
- * in all day boxes and entry lists they will appear in during their lifetime.
- * The idea is that there are probably relatively few repeating entries, and
- * they can be found by following the chain. All other entries can still be
- * found using binary searches.
- * Rebuilding could be part of add_entry(), but that would be inefficient
- * when a file is read in, because then it's sufficient to build the chain
- * once at EOF, not every time an entry is added.
- */
-
- rebuild_repeat_chain(list)
- struct list *list; /* list to delete from */
- {
- register long *prev; /* previous chain pointer */
- register struct entry *ep; /* scan pointer */
- register int n; /* entry counter */
-
- if (list) {
- list->locked++;
- prev = &list->repeating;
- for (n=0, ep=list->entry; n < list->nentries; n++, ep++)
- if (ep->rep_every || ep->rep_weekdays ||
- ep->rep_days || ep->rep_yearly) {
- *prev = n;
- prev = &ep->nextrep;
- }
- *prev = -1;
- list->locked--;
- }
- }
-
-
- /*
- * find an entry with a given time. if <exact> is TRUE, return the index of
- * the first matching entry (this is a straight lookup). If <exact> is FALSE,
- * return the index of the first entry after the last matching entry (this is
- * for inserting, always append if there are multiple actors with the same
- * time). If there is no match, return the index of the first entry with a
- * larger time, regardless of <exact>.
- * If <norep> is TRUE, ignore later instances of repeating entries. This
- * is used when new entries are inserted into the list; when looking up
- * an entry for printing, it is FALSE. Setting <norep> to TRUE also prevents
- * list->repeating to be used before the chain exists.
- * The lookup is a two-step process: entries at a particular date are found
- * using a binary search; the list is sorted by time. Future instances of
- * repeating entries cannot be found that way; they are found by evaluating
- * all repeating entries. Repeating entries are found by following the
- * <nextrep> chain that was built by rebuild_repeat_chain().
- * Return FALSE if the lookup failed, and we fell off the end of the list.
- */
-
- static lookup_regular_entry(), lookup_repeating_entry();
-
- BOOL lookup_entry(lookup, list, time, exact, norep)
- register struct lookup *lookup; /* return struct */
- register struct list *list; /* list of entries */
- time_t time; /* time to locate */
- BOOL exact; /* need entry, not insert pt */
- BOOL norep; /* ignore instances */
- {
- int repindex, regindex;
- time_t reptime = -1, regtime = -1;
-
- list->locked++;
- lookup->regindex = lookup->repindex = -1;
- lookup->regtime = lookup->reptime = 0;
- regindex = lookup_regular_entry(list, time, exact, norep);
- repindex = norep ? -1
- : lookup_repeating_entry(list, time, exact, &reptime);
- if (regindex >= 0)
- regtime = list->entry[regindex].time;
- list->locked--;
-
- if (repindex >= 0 && (regtime < 0 || reptime < regtime)) {
- lookup->index = lookup->repindex = repindex;
- lookup->trigger = lookup->reptime = reptime;
- } else {
- lookup->index = lookup->regindex = regindex;
- lookup->trigger = lookup->regtime = regtime;
- }
- lookup->list = list;
- return(lookup->index >= 0 && lookup->index < list->nentries);
- }
-
-
- static lookup_regular_entry(list, time, exact, norep)
- struct list *list; /* list of entries */
- time_t time; /* time to locate */
- BOOL exact; /* need entry, not insert pt */
- BOOL norep; /* treat repeaters as regular*/
- {
- register struct entry *entry; /* entry array */
- register int lo, hi, mid; /* binary search indices */
-
- entry = list->entry;
- lo = 0;
- hi = list->nentries;
- while (lo < hi) {
- mid = lo + (hi - lo) / 2;
- if (mid == list->nentries || time >= entry[mid].time)
- lo = mid+1;
- else
- hi = mid;
- }
- if (exact)
- while (lo && time == entry[lo-1].time)
- lo--;
- else
- while (lo < list->nentries && time == entry[lo].time)
- lo++;
- if (!norep)
- while (lo < list->nentries && (entry[lo].rep_every ||
- entry[lo].rep_yearly ||
- entry[lo].rep_weekdays ||
- entry[lo].rep_days))
- lo++;
- return(lo < list->nentries ? lo : -1);
- }
-
-
- static lookup_repeating_entry(list, time, exact, reptime)
- struct list *list; /* list of entries */
- time_t time; /* time to locate */
- BOOL exact; /* need entry, not insert pt */
- time_t *reptime; /* returned repeat time */
- {
- register struct entry *entry; /* entry array */
- register int n; /* next repeating entry */
- register time_t earliest = 0; /* earliest future entry yet */
- register int earliest_n= -1; /* index of that entry */
- int prev_n = -1; /* entry before n */
- int earliest_prev_n;/* entry before earliest_n */
- time_t test; /* next repeater trigger */
-
- exact = exact != FALSE;
- for (n=list->repeating; n != -1; prev_n=n, n=entry->nextrep) {
- entry = &list->entry[n];
- if (recycle(entry, time, &test) == 1)
- if (!earliest || test + exact < earliest) {
- earliest = test;
- earliest_n = n;
- earliest_prev_n = prev_n;
- }
- }
- if (earliest_n >= 0 && earliest_prev_n >= 0) {
- list->entry[earliest_prev_n].nextrep =
- list->entry[earliest_n].nextrep;
- list->entry[earliest_n].nextrep = list->repeating;
- list->repeating = earliest_n;
- }
- *reptime = earliest;
- return(earliest_n);
- }
-
-
- /*
- * given an entry, find the entry that triggers next. If there is none,
- * return FALSE.
- * The trigger time of the returned entry is stored in <lookup.trigger>.
- * Never call this when the previous call or lookup_entry() returned FALSE.
- *
- * First, if the previously returned entry was repeating, go to the next
- * repeating entry; if the previously returned entry was regular, go to
- * the next regular entry. Then pick the earlier of the two.
- */
-
- lookup_next_entry(lookup)
- register struct lookup *lookup; /* previously found entry */
- {
- register struct entry *entry; /* entry array */
- register int n; /* next repeating entry */
- int repindex = -1, regindex = -1;
- time_t reptime, regtime;
- struct list *list = lookup->list;
- time_t time = 0;
- int prev_n, earliest_prev_n = -1;
- register time_t earliest = 0;
- register int earliest_n = -1;
-
- /* next repeating */
- prev_n = lookup->repindex >= 0 ? lookup->repindex
- : list->repeating;
- n = prev_n == -1 ? -1 : list->entry[prev_n].nextrep;
- if (lookup->repindex >= 0) {
- prev_n = lookup->repindex;
- n = list->entry[prev_n].nextrep;
- } else {
- prev_n = -1;
- n = list->repeating;
- }
- for (; n != -1; prev_n=n, n=entry->nextrep) {
- entry = &list->entry[n];
- if (recycle(entry, lookup->trigger, &time) == 1)
- if (!earliest || time < earliest) {
- earliest = time;
- earliest_n = n;
- earliest_prev_n = prev_n;
- }
- }
- repindex = earliest_n;
- reptime = earliest;
- entry = &list->entry[n = earliest_n];
- if (n >= 0 && earliest_prev_n >= 0) {
- if (earliest_prev_n == -1)
- list->repeating = entry->nextrep;
- else
- list->entry[earliest_prev_n].nextrep
- = entry->nextrep;
- if (lookup->repindex == -1) {
- entry->nextrep = list->repeating;
- list->repeating = n;
- } else {
- entry->nextrep =
- list->entry[lookup->repindex].nextrep;
- list->entry[lookup->repindex].nextrep = n;
- }
- }
-
- /* next regular */
- if (lookup->regindex < 0) {
- regindex = lookup_regular_entry(list,
- lookup->trigger, TRUE, FALSE);
- regtime = list->entry[regindex].time;
- } else {
- n = lookup->regindex + 1;
- entry = &list->entry[n];
- for (; n < list->nentries; n++, entry++)
- if (!entry->rep_every && !entry->rep_weekdays &&
- !entry->rep_days && !entry->rep_yearly) {
- regindex = n;
- regtime = entry->time;
- break;
- }
- }
- /* use rep or reg */
- if (repindex >= 0 && (regindex < 0 || reptime < regtime)) {
- lookup->index = lookup->repindex = repindex;
- lookup->trigger = lookup->reptime = reptime;
- } else {
- lookup->index = lookup->regindex = regindex;
- lookup->trigger = lookup->regtime = regtime;
- }
- return(lookup->index >= 0 && lookup->index < list->nentries);
- }
-
-
- /*
- * scan main list, and return the next entry. The next entry is the one
- * triggers next for one of three reasons (returned value):
- * 0: no trigger for at least 24 hours after <time>,
- * 1: early_warn of *entryp is nonzero, and early warn time is reached,
- * 2: late_warn of *entryp is nonzero, and late warn time is reached,
- * 3: the alarm time of *entryp is reached.
- *
- * The algorithm uses the fact that no warning can come more than 24 hours
- * before the trigger time. The first entry that is at most 24 hours early
- * is looked up, then the next 72 hours are searched linearly. Events that
- * <triggered> before are ignored. The caller must store the returned reason
- * in (*entryp)->triggered to avoid double triggers, iff the reason is > 0.
- * wait can be negative, up to -ANCIENT, to catch events that were missed.
- *
- * This routine is used by the daemon only. Ignore the lint complaint.
- */
-
- find_next_trigger(list, time, entryp, wait_time)
- struct list *list; /* list of entries */
- time_t time; /* time to locate */
- struct entry **entryp; /* ret: entry that was found */
- time_t *wait_time; /* ret: how long until triggr*/
- {
- BOOL found; /* TRUE if lookup succeeded */
- struct lookup lookup; /* result of entry lookup */
- register struct entry *ep; /* current entry */
- time_t trigger; /* next trigger time of *ep */
- time_t dist; /* time distance to event */
- time_t mindist = MAXT; /* smallest distance so far */
- int reason = 0; /* why is it earliest: 1,2,3 */
-
- if (!list)
- return(0);
-
- found = lookup_entry(&lookup, list, time-ANCIENT, TRUE, FALSE);
- while (found) {
- trigger = lookup.trigger;
- if (trigger > time+2*86400)
- break;
- ep = list->entry + lookup.index;
- if (!ep->suspended && !ep->notime)
- switch (ep->triggered) {
- case 0:
- if (ep->early_warn &&
- trigger - ep->early_warn > cutoff) {
- dist = trigger - ep->early_warn - time;
- if (dist > -ANCIENT && dist < mindist){
- mindist = dist;
- *entryp = ep;
- reason = 1;
- }
- }
- case 1:
- if (ep->late_warn &&
- trigger - ep->late_warn > cutoff) {
- dist = trigger - ep->late_warn - time;
- if (dist > -ANCIENT && dist < mindist){
- mindist = dist;
- *entryp = ep;
- reason = 2;
- }
- }
- case 2:
- if (!ep->noalarm && trigger > cutoff) {
- dist = trigger - time;
- if (dist > -ANCIENT && dist < mindist){
- mindist = dist;
- *entryp = ep;
- reason = 3;
- }
- }
- }
- found = lookup_next_entry(&lookup);
- }
- *wait_time = mindist;
- return(reason);
- }
-
-
- /*----------------------------------- entry mgmt ----------------------------*/
- /*
- * duplicate an entry. This is done when someone begins to edit an entry;
- * the old entry is preserved and stays in the list until the new entry is
- * confirmed (see confirm_new_entry()). If <old> is 0, the new entry is
- * zeroed.
- */
-
- clone_entry(new, old)
- register struct entry *new; /* entry to fill in */
- register struct entry *old; /* entry to clone, or 0 */
- {
- if (!old) { /* zero new entry */
- new->time = 0;
- new->length = 0;
- new->early_warn = 0;
- new->late_warn = 0;
- new->suspended = FALSE;
- new->private = FALSE;
- new->noalarm = FALSE;
- new->notime = FALSE;
- new->triggered = 0;
- new->message = 0;
- new->script = 0;
- new->meeting = 0;
- new->note = 0;
- new->rep_every = 0;
- new->rep_last = 0;
- new->rep_weekdays = 0;
- new->rep_days = 0;
- new->rep_yearly = FALSE;
- return;
- }
- *new = *old; /* copy old to new */
- if (old->message)
- new->message = mystrdup(old->message);
- if (old->script)
- new->script = mystrdup(old->script);
- if (old->meeting)
- new->meeting = mystrdup(old->meeting);
- if (old->note)
- new->note = mystrdup(old->note);
- }
-
-
- /*
- * destroy an entry. De-allocate all memory hanging off it. Don't release
- * the entry itself, it's probably some static buffer.
- */
-
- destroy_entry(entry)
- register struct entry *entry; /* entry to destroy */
- {
- if (entry->message)
- free(entry->message);
- if (entry->script)
- free(entry->script);
- if (entry->meeting)
- free(entry->meeting);
- if (entry->note)
- free(entry->note);
- clone_entry(entry, (struct entry *)0); /* paranoid */
- }
-